package leetcode.editor.cn.dsa15_stackAndGA;
// 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。
// 需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

public class RemoveDuplicateLetters316_1 {
    public static void main(String[] args) {
        Solution solution = new RemoveDuplicateLetters316_1().new Solution();
        System.out.println(solution.removeDuplicateLetters("bcabc")); //abc
        System.out.println(solution.removeDuplicateLetters("cbacdcbc")); //acdb
        System.out.println(solution.removeDuplicateLetters("dcbadd")); //cbad
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String removeDuplicateLetters(String s) {
            int len = s.length();
            // 结束条件：空字符串或者单字符不处理
            if (len <= 1) return s;
            StringBuilder sb = new StringBuilder();
            while (s.length() > 1) {
                // 创建计数器，记录每个字母在字符串中最后一次出现的位置
                int[] lastOccurrence = new int[26];
                for (int i = 0; i < s.length(); i++) {
                    lastOccurrence[s.charAt(i) - 'a'] = i;
                }
                int pos = 0; // 记录当前处理过的字符串中最小的字符位置
                for (int i = 0; i < s.length(); i++) {
                    if (s.charAt(i) < s.charAt(pos))
                        pos = i;
                    // 发现某个字符是最后一次出现，那么满足条件的当前字符串的
                    // 最小字符一定不在后面的子字符串中了，退出循环
                    if (lastOccurrence[s.charAt(i) - 'a'] == i)
                        break;
                }
                sb.append(s.charAt(pos));
                // 继续处理剩下的pos之后的字符串，我们可以把pos之后字符串中
                // 重复出现的s.charAt(pos)字符去除了
                s = s.substring(pos+1)
                        .replaceAll(""+s.charAt(pos), "");
            }
            sb.append(s);
            return sb.toString();
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}